The present invention relates to methods and structures for using an electronic device to accomplish division.
Division is the most costly of fundamental arithmetic operations. It is typically performed iteratively and low-latency division is difficult to achieve due to data dependency between adjacent iterations.
Computers typically use floating-point numbers, which allow for efficient expression of and operation on both very large and very small numbers. Dividing two floating-point numbers requires determining the sign, exponent, and the fractional portion of the quotient. Operations to determine the sign and exponent are very simple, low cost, and fast. However, determining the quotient's fractional portion is much more difficult to do efficiently and quickly. Determining the fractional portion requires dividing two numbers which can be several bits long.
The shift-subtract division algorithm is widely used for low cost division. It generates a one-bit partial quotient after each iteration, but, for standard single precision floating-point numbers, takes 24 iterations to reach a result. The radix-4 (or “SRT”) algorithm provides somewhat higher performance. It produces a two-bit partial quotient after each result and can produce a result for single precision floating-point numbers in 12 iterations. Some algorithms use series and/or Taylor expansion estimation to achieve higher performance, but are either hardware intensive and/or require iterations that make complex calculations insufficiently efficient.
For highly complex calculations, there is a need to find a lower latency and more hardware-efficient solution than the solutions previously known.